The present invention relates to the field of cryptographic protocols in general, and, more particularly, to secure function evaluation with application to the holding of networked auctions by computer.
Many applications involve a group of participants, denoted herein as xe2x80x9cpartiesxe2x80x9d, each of whom has an input to the group as a whole, where the group as a whole is required to compute and output a certain function of these inputs. The term xe2x80x9cfunctionxe2x80x9d herein denotes, in the usual sense, any mathematical or logical mapping from one set of input entities to a output entity or set of entities. In certain cases, the inputs may involve sensitive information, such that it would also be required that this computation does not reveal any information about the inputs, except for whatever might be computed from the final output. Such inputs are herein denoted as xe2x80x9cprivate inputsxe2x80x9d. If, in addition to the parties, there were furthermore a trustworthy participant, denoted herein as a xe2x80x9ccenterxe2x80x9d, and which is trusted by all the parties, then each party could simply send the respective private input to this center, which would then compute the function and publish, or output, the value of the computed function. (The center is a participant in the protocol and is involved in the computation of the function, but has no private input and is not within the group of parties.) The parties, however, might not trust each other, and might not trust any single center.
A particular case of interest is that of auctions. Consider, for example, sealed-bid second-price auctions, commonly known in the art as xe2x80x9cVickrey auctionsxe2x80x9d. In a Vickrey auction, an auctioneer (the center) presents an item for sale to a group of bidders (the parties). Each interested bidder sends a bid to the auctioneer, which is to be kept private from all other bidders, and to be examined by the auctioneer together with all the other bids at the end of the published bidding period. In a Vickrey auction, the winner is the highest bidder, and the winner pays the amount of the second highest bid. The Vickrey auction is a non-interactive sealed-bid simulation of the popular interactive auction method in which the price is raised until only a single bidder remains, commonly known in the art as the xe2x80x9cEnglish auctionxe2x80x9d. In an English auction, the remaining bidder wins the auction and has to pay the price at which he was left as the last bidder. Because the English auction is interactive, constant attention of the bidders is required, and in certain situations it may be desirable to simulate the English auction with the non-interactive Vickrey auction. In a Vickrey auction, the best strategy for a bidder is simply to set his bid to be exactly how much he values the item for sale, thereby greatly reducing the work, attention, and communication needed to conduct and participate in the auction.
The Vickrey auction is thus a highly desirable auction method, but there are certain serious limitations thereto, concerning trust and privacy. For example, note that a corrupt auctioneer can easily cheat by examining the bids before the end of the bidding period and inserting a fake bid which is just slightly lower than the highest bid. This artificially and dishonestly increases the amount that the winner is required to pay. Unlike the English auction, where the bidding is public, the bids in a Vickrey auction are private, so there is currently no way for any of the bidders to individually verify that the auctioneer conducted the auction honestly.
Another limitation of the Vickrey auction involves privacy and stems from the fact that the auctioneer examines all bids and can use the information thereby gathered in order to cheat in future auctions. Suppose, for example, that at the end of an auction the auctioneer learns that the highest bidder valued the item for sale at $1000. Then, if the auctioneer subsequently auctions a second such item (even in a non-Vickrey auction, such as an English auction) and the highest bidder from the previous auction participates in this subsequent auction as well, the auctioneer can insert fake bids which are very close to $1000 with the intention of dishonestly increasing the amount the winner would have to pay. Because the auctioneer has obtained this information in advance of the subsequent auction, the fake bids could even be inserted by other dishonest bidders during the auction, in collusion with the auctioneer.
The potential for frauds of this sort deters many parties from participating in such auctions, or at least in auctions that are not run by highly respectable auctioneers. The value of auction methods such as the Vickrey auction is great enough that it is desirable to have a way for each of the bidders to individually verify that the auction was conducted honestly, and in such a way that the auctioneer does not acquire information from the bidders that could be used for dishonest purposes.
Another closely-related application is mechanism design, which deals with the design of protocols for selfish parties. The goal of a protocol is to aggregate the preferences of the parties in order to decide on some social choice (for example, to decide whether a community should build a bridge, or how to route packets in a network, or to decide who wins an auction). Each party has a utility function which expresses how much that party values each possible outcome of the protocol (the bid in an auction, for example, is such a utility function). Each party sends information about its utility function to a center, which decides on the outcome of the protocol based on the reports from the parties, according to a specified function of the utility functions (for example, in a sealed-bid auction, the specified function that determines the winner is the maximum of the bids). Of course, a party might choose to report according to a false utility function if some benefit can be derived therefrom (for example, by submitting a fake bid at an auction, in collusion with a dishonest auctioneer, as described above). The goal is to come up with mechanism designs in which it is not beneficial for any party to report a false utility function.
The xe2x80x9crevelation principlexe2x80x9d states that for any mechanism there is a direct, incentive-compatible mechanism with the same result. That is, that there is an equivalent mechanism in which the optimal strategy for each party is to report the true utility function. It is often assumed that the center can be trusted by the parties, but this might not always be true, especially in an Internet setting. The revelation principle might not be valid if the center is corrupt and misuses the truthful utility functions that are received. Keeping the utility function private from the center is therefore essential in order to ensure the center""s honesty.
Various approaches to this general problem appear in the prior art, as proposed in the field of cryptographic research pertaining to secure function evaluation. For any function ƒ(x1, x2, . . . , xn) it is possible in principle to construct a protocol that allows a group of n parties, where party i has as its private input xi, to jointly evaluate ƒ(x1, x2, . . . , xn). Following the completion of the protocol, the parties learn ƒ(x1, x2, . . . , xn) but no party i can learn more about the other private inputs beyond what can be computed from xi and ƒ(x1, x2, . . . , xn).
(The subscript notation of form xe2x80x9cxixe2x80x9d as used herein also appears in some related documents in the equivalent form xe2x80x9cx.sub.ixe2x80x9d. Likewise, the superscript notation of form xe2x80x9cxixe2x80x9d as used herein also appears in some related documents in the equivalent form xe2x80x9cx.sup.ixe2x80x9d.)
Since conducting an auction is an evaluation of a function of the bids (the private input utility functions), it is tempting to employ such a protocol in implementing auctions. However, the drawback is that these protocols are rather complex and require a lot of interaction between the parties. In the case of auctions, this would require high interaction between the bidders, who have no motivation to interact with each other. Furthermore, these protocols are secure only so long as less than a certain threshold of the bidders do not collude maliciously, and this is a weakness of these protocols, because it may be difficult or impossible to assure that such collusion does not occur. Such a protocol could be attacked, for example, by packing an auction with a suitably-large number of dishonest bidders who collude among themselves.
There also appears in the prior art methods for distributing the operation of an auctioneer between many servers in a way that is secure so long as not too many of these servers collude. Such a scheme is disclosed, for example, in xe2x80x9cThe Design and Implementation of a Secure Auction Serverxe2x80x9d, by M. K. Franklin and M. K. Reiter, IEEE Transactions on Software Engineering, 22(5), pp. 302-312, 1996. Such a distributed system for sealed-bid auctions with many auctioneer servers ensures that the auctioneer servers do not learn the bids, but only until the time the bids are opened. Protocols of this sort are also the basis for the auction protocols disclosed in xe2x80x9cElectronic Auctions wit Private Bidsxe2x80x9d, by M. Harkavy, J. D. Tygar and H. Kikuchi, 3rd USENIX Workshop on Electronic Commerce, pp. 61-73, 1999, which enables systems for secure fist-price and second-price sealed-bid auctions that preserve the privacy of the bids even after the winning bid is chosen. These systems distribute the operation of the auctioneer among several auctioneer servers, wherein privacy is guaranteed so long as not too many of the auctioneer servers collude. Most of the protocols require that fewer than one-third of the auctioneer servers collude, and therefore need a minimum of four auctioneer servers. As with the protocols specifying a threshold of colluding bidders, it is difficult or impossible to assure that such collusion does not occur in these systems based on auctioneer servers.
U.S. Pat. No. 5,905,975 to Ausubel discloses a method for auctioning multiple, dissimilar items without the value of highest (winning) bid becoming known to the auctioneer, by implementing the well known Groves-Clarke mechanism. Limitations of the Ausubel method, however, include the requirement for multiple rounds of communication between the participants in the auction, and less than optimal privacy for the bidders.
A related invention by the present inventors, xe2x80x9cHonesty Preserving Negotiation and Computationxe2x80x9d, which is the subject of a separate patent application, introduces a method for ensuring the honesty of the center, and may be applied in a scenario in which each of the parties sends a private input to the center, which then computes and publishes the output of the function. This method enables the center to prove that the function was computed correctly, without requiring publication of the private inputs received from the parties. A limitation of this method, however, is that the center learns the private inputs of the parties. In an auction conducted according to this method, the auctioneer would learn the individual bids of each of the bidders.
Further limitations of the prior art involve the high interactivity required among the bidders and/or servers. The Franklin and Harkavy systems require bidders to communicate directly with all the servers. Furthermore, the Harkavy systems require high interactivity between the servers over many rounds of interaction. These requirements impose bandwidth and latency constraints and essentially imply that all servers be physically controlled by the same organizationxe2x80x94in other words, the auctioneer. In such a case, privacy is attainable only if the auctioneer can be trusted not to combine the information held by these different servers. Such an assumption is not enforceable and cannot be verified by an outsider. The only meaningful protection afforded by such protocols is therefore against external break-in to the auctioneer""s servers (assuming also that not too many of them are successfully attacked). This architecture therefore requires complete trust in the auctioneer, which might not be justified, for example, in the case of small Internet auctioneers. These limitations of the prior art methods are such that they are not practical for implementing trusted auctions.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method and system by which a center can compute and publish a specified function of a set of utility functions provided by a set of independent parties, whereby the utility functions remain private, the parties can independently verify that the specified function has been computed correctly, the interactions within the center and its components are limited, the parties do not need to engage in interactions among themselves, the amount of intercommunication among the participants remains within a reasonable limit, and wherein the center acquires no information about the individual utility functions themselves. This goal is met by the present invention.
The present invention is of a method and system for allowing any number of parties, via a center, to collectively compute any function in a manner that preserves the privacy of the individual private inputs of the parties to the collective computation, even after the computation of the function has been completed, and in such a way that each party can independently verify that the function was computed correctly. The present invention requires only a modest amount of interaction, does not require that the parties interact with one another, and does not require that the center be distributed among non-colluding servers. Furthermore, the present invention can be used to implement general mechanisms and to compute general functions.
The term xe2x80x9cprotocolxe2x80x9d herein denotes a complete and unambiguous method for accomplishing a purpose, whose steps specify a series of formal interactions in a required sequence which involve exchanges of information and computational steps on the information by two or more distinct individual entities, herein denoted as xe2x80x9cparticipantsxe2x80x9d; all of whom fully know the method and agree to follow the specified steps thereof. The method according to the present invention is such a protocol, wherein the distinct participants include, but are not limited to, the parties, an issuer, and the center. The term xe2x80x9cinputxe2x80x9d herein denotes information that is furnished to the protocol by one or more of the participants. Information furnished as an input to the protocol does not necessarily become available to any specified participant, however. Likewise, the term xe2x80x9coutputxe2x80x9d herein denotes information that is furnished by the protocol to one or more of the participants. Information furnished as an output by the protocol also does not necessarily become available to any specified participant. The purpose of this protocol is to compute a function in a way that can be verified individually by the participants, while imposing a well-defined limitation on the flow of information among the participants in terms of content and ultimate destination, including the generation and flow of meta-information (i.e., information about the information exchanged in the protocol), in order to preserve the privacy of the participants. It might be possible to interrupt the protocol, so that the desired function computation and flow of information is prevented, but a goal of the present invention is to make it statistically impossible, when operating within a set of constraints specified by the protocol, to defeat the privacy-protecting limitations of the protocol or to force a false computation of the function that would be undetectable to the participants. The constraints of the protocol include the requirement that certain specified participants do not collude to exchange information separate from the protocol. The term xe2x80x9cattackxe2x80x9d herein denotes any stratagem or method intended to defeat the limitations of the protocol.
Consider a scenario with N parties, each having a private input, and a center which should compute a function ƒ of these private inputs (for example ƒ can be the maximum of all the private inputs). The term xe2x80x9cprivate inputxe2x80x9d herein denotes an input by a specific participant which is intended not to be generally available to any other participant. The present invention enables the center to compute and publish the output of ƒ and to prove to all parties that it computed ƒ correctly, but without revealing any information about the private inputs to the center or to any party, even after the value of ƒ is published.
The present invention achieves these properties by adding another participant, denoted herein as the xe2x80x9cissuerxe2x80x9d, who generates a description corresponding to the function which allows computing the function (such as a program or circuit which evaluates the function), but who does not take any other active part in the protocol. In operation, the center and the issuer jointly evaluate the function using a secure two-party function evaluation in which only the center learns the output of the function, but the center does not learn the values of the inputs to the function. Since both the center and the issuer each learn only portions of the inputs, neither of them learns the inputs. In the case of auctions, as long as the auctioneer (the center) and the issuer do not collude, then neither of them learns any information about the bids (the private inputs), even after the auction is over. The protocols do not require any communication between the bidders and the issuer, and the computational efficiency is very high.
In particular, the parties can be bidders in an auction, their private inputs are their bids, the center is the auctioneer, and the function ƒ is the rule by which the outcome of the auction is decided. The present invention enables the auctioneer to compute the result of the auction without learning any information about the bids, except for the identity of the winner, and the amount the winner has to pay.
One of the embodiments of the present invention is a system for computing second-price sealed-bid auctions (Vickrey auctions). However the system can be used to privately implement other mechanisms, such as first-price or kth price auctions, auctions with reservation prices, double-auctions (where there are many sellers), generalized Vickrey auctions, Groves-Clarke mechanisms, and the like. Furthermore it is possible to use the method of the present invention for tasks such as stable matching (such as for residents and hospitals), and for decision-making.
Advantages of the present invention over the prior art include:
1. The center computes the function without leaning any information about the private inputs, except for the final output of the function. This property holds even after the center computes the value of the function. The method according to the present invention thus ensures the privacy of the parties from the center and from all the other parties. In the case of auctions, this property is important when the same auctioneer performs several auctions. If the auctioneer learns the values of the bids in an initial auction, this information can be used dishonestly to increase the amount that winners have to pay in the subsequent auctions. The privacy property of the present invention prevents such behavior by the auctioneer.
2. The center can prove that it computed the function correctly, even though it does not know the values of the private inputs of the different parties.
3. Neither the center nor the issuer can learn by itself any information about the private inputs of the parties. Only if the center and the issuer collude can any information be learned about the private inputs. The private inputs are therefore essentially locked in a vault with two locks, with one key being held by the center and the other key held by the issuer. In the case of a sealed-bid auction, the method according to the present invention enables the implementation of a sealed-bid auction electronically, while ensuring that the auctioneer cannot cheat and does not even learn the values of the bids.
4. The security and reliability of the method according to the present invention do not require trust in any party. It is required only that the center and the issuer do not collude.
5. There are no disputes. All parties can verify that the center computed the function correctly and that the issuer did not cheat.
6. The method according to the present invention requires very little interaction: only a few messages need to be exchanged between the center and each of the parties, and between the center and the issuer. In particular, the number of rounds of communication is constant and does not depend on the number of parties. No communication is required among the parties themselves, nor between any party and the issuer.
7. The method can be applied to many variants of the function ƒ, such as for first-price auctions, second-price auctions, or for double auctions. The function ƒ can also be for a mechanism design, for polling opinions, for computing a stable matching, and for other applications.
8. The function ƒ can be defined to reveal some information about the inputs. For example the output of ƒ can include some statistics of the private inputs, such as the mean or variance.
A goal of the present invention is to minimize the trust that bidders are required to put in the auctioneer in sealed-bid auctions as well as in more general mechanisms. This goal is especially important in online auctions where there are seldom any long-term relationships between bidders and auctioneers, and where there may be many small-scale auctioneers that offer auctions of different sorts.
Another goal of the present invention is to control and restict the nature and amount of information that becomes known to the auctioneer in the course of conducting an auction. For example in the case of second-price auctions the auctioneer should learn the identity of the highest bidder (but not his bid!) along with the clearing price, which is the amount the winner has to pay, in this case the second-highest bid. Neither the bidders nor the auctioneer, however, should learn the identity of the second-highest bidder, nor any information about the other bids. The present invention, in fact, offers bidders better privacy in the above respects than suctions conducted in the physical realm, where sealed-bid auctions are carried out using bid written on paper and enclosed in sealed envelopes. Still, all the bidders should be able to verify that the auction was run correctly, that the highest bidder won, and that the clearing price is correct.
Despite the need for privacy in the bidding, there are aspects of the bids that are of legitimate interest to auctioneers. This information, for example, might concern the statistics of the bids, and could be valuable in attracting sellers and buyers to the auctions. Therefore, a further goal of the present invention is to allow an auctioneer to use the bids to gather useful and legitimate information. There might be a tension between the bidders, who prefer that the auctioneer not learn any information but the outcome of the auction, and the auctioneer, who prefers to gather as much information as possible. Accordingly, the present invention enables control of exactly what information becomes known to the auctioneer. For example, the auctioneer might be allowed to learn some aggregate statistics of the bids (e.g. the average bid, or the percentage of bids within a certain range), while still being prevented from learning the identity of the bidders who are associated with a certain bid or range of bids. All such variants can be easily incorporated into the scheme.
The method according to the present invention employs several techniques developed for two-party secure function evaluation and achieves efficient communication in multiparty protocols, such as in multi-party protocols for auctions, by assigning different roles to the parties, the center, and the issuer.
The invention involves several entities, as described and illustrated below in terns of the non-limiting special case of auctions. As noted previously, the method according to the present invention is applicable to many different situations. In the case of auctions, the parties are bidders, and the center is the auctioneer. The present invention operates in the general case in a manner similar to that of the special case of auctions. Described and illustrated herein are the main components, along with the trust and complexity requirements of the protocol.
The different participants in a secure multi-party function evaluation according to the present invention are depicted in FIG. 1, in terms of the non-limiting special case of auctions. In one of the embodiments, there is an issuer 102; at least one auctioneer, such as an auctioneer 104, an auctioneer 106, and an auctioneer 108; and at least two bidders, such as a bidder 110, a bidder 112, and a bidder 114.
Bidders: Many bidders may participate. In the simplest case one or some of the bidders are parties who wish to sell items, and the rest of the bidders are interested in buying these items. In the general case the bidders are parties who should allocate some resources using a predefined mechanism. The bidders send a message to an auctioneer, which describes (in an xe2x80x9cencryptedxe2x80x9d way) a utility function (the private input), and at the end of the protocol they can verify the operation of the auctioneer. In a variation, the bidders are sellers and the auctioneer is the buyer.
Auctioneer: The auctioneer promotes the auction, such as by advertising, receives the bids from the bidders, communicates with the issuer, and computes the output of the protocol. The auctioneer might be a party which merely organizes the auction or the mechanism, but also might be one of the bidders (for example the auctioneer might be selling an item which all other bidders are interested in buying). The present invention allows the auctioneer to participate in the auction as a bidder without creating a conflict of interest or giving the auctioneer an unfair advantage. The present invention ensures that the auctioneer cannot learn by itself any information about the bids, except for computing the desired outcome of the protocol.
Issuer: The issuer creates a coded program that computes the output of the protocol in a way that preserves privacy, and finishes the coded program to the auctioneer. The preparation of the coded program can be done prior to the auction, and does not depend on the identities of the auctioneer or the bidders. The issuer does not interact with the bidders, and performs only a single one-round interaction with the auctioneer after the auctioneer receives the bids. The issuer is therefore a service provider which provides coded programs for many auctions carried out by many auctioneers.
Consider an ideal model in which there is an auctioneer who is fully trusted by all the bidders. There is a trivial way to perform an auction in this model: all bidders send their bids to the trusted auctioneer, who then computes and outputs the results. Note that even in this model some information is leaked about the bids. For example the highest bidder and the clearing price might be published. At the other extreme, this information might be only revealed to the highest bidder and to the seller. There are many possible variations regarding the information that is learned by different parties. Even here, the winner learns that he met the winning criteria, which itself reveals some information about the other bids, but this is inevitable.
The protocol of the present invention provides the highest degree of privacy, by ensuring that no party learns more information than would be learned in the ideal model. Even the auctioneer or the issuer cannot learn more than in the ideal model. As presented herein, the protocol differs from that of the ideal model, in that the issuer is able to learn the number of bidders. It is easy to prevent this, however, if there is a bound on the number of bidders.
Only if both the auctioneer and the issuer collude can the privacy of the bidders be compromised. Bidders need only trust that the issuer and the auctioneer do not collude to learn their bids, and are assured that the issuer or the auctioneer alone cannot learn more than in the ideal model. A coalition of the auctioneer with several bidders is also no more powerful than in the ideal model, and cannot learn the bids of other bidders. The bidders are therefore required to have a lesser amount of trust in these parties than in their banks, credit card companies, or in the companies that supply their software. The auctioneer can be any party that wishes to organize an auction, while the issuer should typically be an established party like a financial institution or a large company, which supplies services to many auctioneers. The issuer does not perform any communication with the bidders, but only with the auctioneers. This is of benefit to the auctioneers, because there is no risk that the issuer might take away the auctioneers"" customers.
It is required that the public key of the issuer be known to the bidders. Besides this, there is no requirement for any Public Key Infrastructure (PKI).
The communication flow among the participants of the system according to the present invention for a single issuer and single auctioneer is illustrated in FIG. 2. Issuer 102 receives information from an auctioneer 202 via a path 212 and sends information to auctioneer 202 via a path 210. Bidder 110 sends information to auctioneer 202 via a path 204, bidder 112 sends information to auctioneer 202 via a path 206, and bidder 114 sends information to auctioneer 102 via a path 208.
The steps of the method according to the present invention for a single issuer and a single auctioneer are shown in FIG. 3, which also illustrates conceptually the information objects generated and transmitted as part of the protocol.
In a step 302, the auctioneer publishes an invitation for bidders to participate in the auction. Details of this publication include the items for sale, rules by which the winning bids are chosen, minimum bids (if any), the closing time by which bids are due, and the issuer supporting the auction. In a step 304, the bidders prepare their bids and put them into a message 308 which contains a first portion 312 encrypted with a public key 306 belonging to the issuer along with a second portion 310 which may be read by the auctioneer. In a step 314 the bidders submit these messages to the auctioneer. Because portion 312 of message 308 is encrypted using a non-malleable encryption with issuer public key 306, the auctioneer cannot learn from message 308 the content of the bids. Following this, in a step 316, the auctioneer sends encrypted portion 312 to the issuer. Because the issuer does not receive the entire message 308, but only portion 312 thereof, the issuer cannot learn the content of the bids, either. In a step 318 the issuer generates a combinatorial circuit, herein denoted as a xe2x80x9ccircuitxe2x80x9d, such as a circuit 320 to compute the outcome (output) of the auction. Circuit 320 is made of Boolean gates (such as AND, OR, and NOT) that perform this task. The term xe2x80x9cgatexe2x80x9d herein denotes any such device, real or virtual, which has at least one input each having at least two distinct states, and at least one output having at least two distinct states, and such that the output is a well-defined function of the inputs. The function evaluated by the present invention can be any function which can be evaluated by a circuit of gates, herein denoted as a circuit xe2x80x9ccorresponding toxe2x80x9d the function. Circuit 320 is not a physical circuit but in effect an equivalent description of such a circuit which can be used to simulate the operation of such a circuit. The issuer then garbles circuit 320 according to a secure function evaluation protocol, as described in detail below. In a step 322 the issuer also decrypts message 312 and in a step 324 uses the decrypted results to similarly compute garbled inputs to circuit 320. In a step 328 the issuer prepares a signed translation table 330 which decrypts the output of the garbled circuit having inputs 326. In a step 332, the issuer sends garbled circuit and inputs 326 and signed translation table 330 to the auctioneer. Next, in a step 334, the auctioneer uses garbled circuit and message 310 and inputs 326 and signed translation table 330 to compute the results of the auction, and in a step 336, the auctioneer publishes the auction results, along with signed translation table 330.
It should be noted that the only additional communication channel required by this protocol (compared to a protocol with no security at all) is for a single round of communication between the auctioneer and the issuer after receipt of the bids. Furthermore, as is depicted in FIG. 3, the issuer can generate circuit 320 in step 318 and produce a garbled version thereof in advance of the auction, and send the garbled circuit to the auctioneer even before the auction begins, such as on a DVD or another mass storage device. This message with the garbled circuit contains the bulk of the communication required by the protocol.
Therefore, according to the present invention there is provided a method for the secure evaluation of a function by a group of participants, wherein each of a plurality of parties furnishes a private input to the function, and wherein, except for what may be deduced from the output of the function, the function is evaluated without any participant learning any information about the private input of any other participant, the method including the steps of: (a) providing an issuer as a participant, the issuer being operative to preparing a description corresponding to the function; (b) providing a center as a participant, the center being operative to evaluating the function from the description; (c) each of the plurality of parties sending a private input such that only the issuer learns a first portion of the private input, and such that only the center learns a second portion of the private input, wherein both the first portion and the second portion are necessary to learn the private input; and (d) the issuer and the center evaluating the function from the description by engaging in a secure two-party function evaluation, such that only the center learns the output of the function, and such that the center does not learn the private inputs thereto.
Furthermore according to the present invention there is also provided a method for Proxy Oblivious Transfer of a selection by a first participant from an ordered set prepared by a second participant to a third participant, wherein the third participant learns the selected item of the set but does not learn the order of the selection, the first participant learns nothing, and the second participant learns nothing, the method including the steps of: (a) the first participant preparing a plurality of public keys, one for every possible selection, and a private key corresponding only to the actual selection thereof; (b) the second participant preparing a plurality of encryptions, one of each of the ordered set, using the corresponding public key of the plurality of public keys; and (c) the third participant decrypting the plurality of encryptions with the private key to recover the selected item.